package com.xgh.link;

import com.xgh.ListNode;

import java.util.HashMap;
import java.util.Map;

/**
 * @ClassName Link2
 * @Description
 * @Author xinggh
 * @Date 2020/7/18 0:03
 * @Version 1.0
 **/
public class Link2 {
    /**
     * 面试题 02.08. 环路检测
     * 给定一个有环链表，实现一个算法返回环路的开头节点。
     * 有环链表的定义：在链表中某个节点的next元素指向在它前面出现过的节点，则表明该链表存在环路。
     * <p>
     * <p>
     * 示例 1：
     * <p>
     * 输入：head = [3,2,0,-4], pos = 1
     * 输出：tail connects to node index 1
     * 解释：链表中有一个环，其尾部连接到第二个节点。
     * <p>
     * 示例 2：
     * <p>
     * 输入：head = [1,2], pos = 0
     * 输出：tail connects to node index 0
     * 解释：链表中有一个环，其尾部连接到第一个节点。
     * <p>
     * 示例 3：
     * <p>
     * 输入：head = [1], pos = -1
     * 输出：no cycle
     * 解释：链表中没有环。
     *
     * @param head
     * @return
     */
    public ListNode detectCycle(ListNode head) {
        if (head == null) {
            return null;
        }

        Map<Integer, ListNode> map = new HashMap<>();
        ListNode l = head;
        while (l != null) {
            if (map.containsKey(l.val)) {
                return map.get(l.val);
            } else {
                map.put(l.val, l);

            }
            l = l.next;

        }
        return null;
    }
}
